{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find Lucky Integer in an Array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #counting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #计数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findLucky"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #找出数组中的幸运数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>在整数数组中，如果一个整数的出现频次和它的数值大小相等，我们就称这个整数为「幸运数」。</p>\n",
    "\n",
    "<p>给你一个整数数组 <code>arr</code>，请你从中找出并返回一个幸运数。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>如果数组中存在多个幸运数，只需返回 <strong>最大</strong> 的那个。</li>\n",
    "\t<li>如果数组中不含幸运数，则返回 <strong>-1 </strong>。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>arr = [2,2,3,4]\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>数组中唯一的幸运数是 2 ，因为数值 2 的出现频次也是 2 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>arr = [1,2,2,3,3,3]\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>1、2 以及 3 都是幸运数，只需要返回其中最大的 3 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>arr = [2,2,2,3,3]\n",
    "<strong>输出：</strong>-1\n",
    "<strong>解释：</strong>数组中不存在幸运数。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>arr = [5]\n",
    "<strong>输出：</strong>-1\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 5：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>arr = [7,7,7,7,7,7,7]\n",
    "<strong>输出：</strong>7\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= arr.length &lt;= 500</code></li>\n",
    "\t<li><code>1 &lt;= arr[i] &lt;= 500</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-lucky-integer-in-an-array](https://leetcode.cn/problems/find-lucky-integer-in-an-array/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-lucky-integer-in-an-array](https://leetcode.cn/problems/find-lucky-integer-in-an-array/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,2,3,4]', '[1,2,2,3,3,3]', '[2,2,2,3,3]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "from typing import DefaultDict\n",
    "\n",
    "class Solution:\n",
    "    def findLucky(self, arr: List[int]) -> int:\n",
    "        count: Dict[int, int] = Counter(arr)\n",
    "        lucky_ints: List[int] = [\n",
    "            n for n, c in count.items() if n == c\n",
    "        ]\n",
    "        return max(lucky_ints) if len(lucky_ints) > 0 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def findLucky(self, arr: List[int]) -> int:\n",
    "        c = Counter(arr)\n",
    "        x = -1\n",
    "        for i in sorted(c.keys()):\n",
    "            if c[i] == i:\n",
    "                x = i\n",
    "        return x\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLucky(self, arr: List[int]) -> int:\n",
    "        from collections import Counter\n",
    "        count = Counter(arr)\n",
    "        ans = -1\n",
    "        for i in count:\n",
    "            if i == count[i]:\n",
    "                ans = max(ans, i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef findLucky(self, s: List[int]) -> int:\n",
    "\t\tl = [0] * 501\n",
    "\t\tfor x in s:\n",
    "\t\t\tl[x] += 1\n",
    "\t\tfor i in range(500,0,-1):\n",
    "\t\t\tif(i == l[i]):\n",
    "\t\t\t\treturn i\n",
    "\t\treturn -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLucky(self, arr: List[int]) -> int:\n",
    "\n",
    "        arr, res = collections.Counter(arr), []\n",
    "\n",
    "        for key,value in arr.items():\n",
    "            if key == arr[key]:\n",
    "                res.append(key)\n",
    "\n",
    "        return max(res) if res else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLucky(self, arr: List[int]) -> int:\n",
    "        # hash映射\n",
    "        data = [0 for x in range(501)]\n",
    "        for a in arr:\n",
    "            data[a] += 1\n",
    "        for k in range(len(data)-1, 0, -1):\n",
    "            if data[k] == k:\n",
    "                return k\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLucky(self, arr: List[int]) -> int:\n",
    "        sheet = dict()\n",
    "        for m in arr:\n",
    "            sheet.setdefault(m,0)\n",
    "            sheet[m]+=1\n",
    "        ans = -1\n",
    "        for s in sheet:\n",
    "            if s == sheet[s]:\n",
    "                ans = max(s,ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLucky(self, arr: List[int]) -> int:\n",
    "\n",
    "        rec = collections.defaultdict(int)\n",
    "        for num in arr:\n",
    "            rec[num] += 1\n",
    "        \n",
    "        lucky = []\n",
    "        for i in arr:\n",
    "            if i == rec[i]:\n",
    "                lucky.append(i)\n",
    "        \n",
    "        if not lucky:\n",
    "            return -1\n",
    "        \n",
    "        return max(lucky)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLucky(self, arr: List[int]) -> int:\n",
    "        x = set()\n",
    "        for num in arr:\n",
    "            # print(arr.count(num))\n",
    "            if num == arr.count(num):\n",
    "                x.add(num)\n",
    "        if x == set():\n",
    "            return -1\n",
    "        else:\n",
    "            return max(x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLucky(self, arr: List[int]) -> int:\n",
    "        res = -1\n",
    "        def get_cnt(arr: List[int], target:int) -> int:\n",
    "            cnt = 0\n",
    "            for item in arr:\n",
    "                if item == target:\n",
    "                    cnt += 1\n",
    "            return cnt\n",
    "        for item in arr:\n",
    "            if get_cnt(arr, item) == item:\n",
    "                if item >= res:\n",
    "                    res = item\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLucky(self, arr: List[int]) -> int:\n",
    "        hs = {}\n",
    "        for n in arr:\n",
    "            if n not in hs: hs[n] = 1\n",
    "            else: hs[n] += 1\n",
    "        ans = -1\n",
    "        for key, value in hs.items():\n",
    "            print(key, value)\n",
    "            if key==value and key>ans:\n",
    "                ans = key\n",
    "        return ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLucky(self, arr: List[int]) -> int:\n",
    "        arr.sort()\n",
    "        i = 0\n",
    "        now = arr[0]\n",
    "        cnt = 0\n",
    "        ma = -1\n",
    "        while i < len(arr):\n",
    "            print(now, ma)\n",
    "            if arr[i] != now:\n",
    "                if cnt == now:\n",
    "                    ma = cnt\n",
    "                now = arr[i]\n",
    "                cnt = 1\n",
    "            else:\n",
    "                cnt += 1\n",
    "            i += 1\n",
    "        if cnt == now:\n",
    "            ma = cnt\n",
    "        return ma"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLucky(self, arr: List[int]) -> int:\n",
    "        f=[0]*(max(arr)+1)\n",
    "        a=-1\n",
    "        for n in range(len(arr)):\n",
    "            f[arr[n]]+=1\n",
    "        print(f)\n",
    "        for i in range(max(arr)+1):\n",
    "            if i>0 and i==f[i]:\n",
    "                a=i\n",
    "        return a\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLucky(self, arr: List[int]) -> int:\n",
    "        cnt = [0] * 501\n",
    "        for num in arr:\n",
    "            cnt[num] += 1\n",
    "        for i in range(500, 0, -1):\n",
    "            if cnt[i] == i:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLucky(self, arr: List[int]) -> int:\n",
    "        cnt=Counter(arr)\n",
    "        ans=-1\n",
    "        for c in cnt:\n",
    "            if c==cnt[c]:\n",
    "                ans=max(ans,c)\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
